"""
https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

315. 计算右侧小于当前元素的个数
困难
相关标签
相关企业
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

 

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2：

输入：nums = [-1]
输出：[0]
示例 3：

输入：nums = [-1,-1]
输出：[0,0]
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
"""

from typing import List


class Solution:

    def merge_sort(self,left_nums:List[List[int]],right_nums:List[List[int]])->List[List[int]]:
        res=[]
        lidx=ridx=0
        while lidx<len(left_nums) and ridx<len(right_nums):
            if left_nums[lidx][0]<=right_nums[ridx][0]:
                res.append(left_nums[lidx])
                left_nums[lidx][1]+=ridx
                lidx+=1
            else:
                res.append(right_nums[ridx])
                ridx+=1
            
        while lidx<len(left_nums):
            res.append(left_nums[lidx])
            left_nums[lidx][1]+=ridx
            lidx+=1
        
        while ridx<len(right_nums):
            res.append(right_nums[ridx])
            ridx+=1

        return res

    def merge(self,nums:List[List[int]],left:int,right:int):
        """
        左闭右开
        """
        if left+1==right:
            return [nums[left]]
        
        mid=(left+right)//2
        left_split=self.merge(nums,left,mid)
        right_split=self.merge(nums,mid,right)

        return self.merge_sort(left_split,right_split)

    def countSmaller(self, nums: List[int]) -> List[int]:
        """
        利用合并排序的特性
        在合并排序的合并环节，比a小的值排序到a之前时，总能得到其中的次数，不论前后
        所以一个关键在于如何记录这个次数，可使用一个数组替换原来的单元素
        """

        cache=[[v,0,i] for i,v in enumerate(nums)]
        temp_res=self.merge(cache,0,len(cache))

        res=[0 for _ in nums]
        for [v,c,i] in temp_res:
            res[i]=c

        return res

if __name__=='__main__':
    s = Solution()
    nums = [-1,-1]
    res=s.countSmaller(nums)
    print(res)
    pass